package leetcode.dp;

import java.util.List;
import java.util.stream.IntStream;

public class Triangle120 {
    class Solution1 {
        public int minimumTotal(List<List<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0 || triangle.get(0) == null || triangle.get(0).size() == 0) {
                return 0;
            }
            int m = triangle.size();
            int n = triangle.get(triangle.size() - 1).size();
            int[][] dp = new int[m][n];
            dp[0][0] = triangle.get(0).get(0);
            for (int i = 1; i < m; i++) {
                for (int j = 0; j <= i; j++) {
                    if (j != 0 && j != i) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);
                    } else if (j == 0) {
                        dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
                    } else if (j == i) {
                        dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
                    }
                }
            }
            return IntStream.of(dp[m - 1]).min().getAsInt();
        }
    }


    //滚动数组
    class Solution2 {
        public int minimumTotal(List<List<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0 || triangle.get(0) == null || triangle.get(0).size() == 0) {
                return 0;
            }
            int m = triangle.size();
            int n = triangle.get(triangle.size() - 1).size();
            int[] dp = new int[n];
            dp[0] = triangle.get(0).get(0);
            for (int i = 1; i < m; i++) {
                for (int j = i; j >= 0; j--) {
                    if (j == i) {
                        dp[j] = dp[j - 1] + triangle.get(i).get(j);
                    } else if (j != 0) {
                        dp[j] = Math.min(dp[j], dp[j - 1]) + triangle.get(i).get(j);
                    } else {
                        dp[j] += triangle.get(i).get(j);
                    }
                }
            }
            int min = Integer.MAX_VALUE;
            for (int d : dp) {
                min = Math.min(min, d);
            }
            return min;
        }
    }

    class Solution3 {
        public int minimumTotal(List<List<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0 || triangle.get(0) == null || triangle.get(0).size() == 0) {
                return 0;
            }
            int m = triangle.size();
            int n = triangle.get(triangle.size() - 1).size();
            int[][] dp = new int[2][n];
            dp[0][0] = triangle.get(0).get(0);
            for (int i = 1; i < m; i++) {
                for (int j = 0; j <= i; j++) {
                    if (j != 0 && j != i) {
                        dp[i & 1][j] = Math.min(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - 1]) + triangle.get(i).get(j);
                    } else if (j == 0) {
                        dp[i & 1][j] = dp[(i - 1) & 1][j] + triangle.get(i).get(j);
                    } else if (j == i) {
                        dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + triangle.get(i).get(j);
                    }
                }
            }
            return IntStream.of(dp[(n - 1) & 1]).min().getAsInt();
        }
    }

    //空间复杂度为 O(1) 的解法
    class Solution4 {
        public int minimumTotal(List<List<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0 || triangle.get(0) == null || triangle.get(0).size() == 0) {
                return 0;
            }
            int n = triangle.size();
            for (int i = 1; i < n; i++) {
                for (int j = i; j >= 0; j--) {
                    if (j == i) {
                        triangle.get(i).set(j, triangle.get(i - 1).get(j - 1) + triangle.get(i).get(j));
                    } else if (j != 0) {
                        triangle.get(i).set(j, Math.min(triangle.get(i - 1).get(j), triangle.get(i - 1).get(j - 1)) + triangle.get(i).get(j));
                    } else {
                        triangle.get(i).set(j, triangle.get(i - 1).get(j) + triangle.get(i).get(j));
                    }
                }
            }
            int min = Integer.MAX_VALUE;
            for (int cur : triangle.get(n - 1)) {
                min = Math.min(min, cur);
            }
            return min;
        }
    }
}
